TNotes.leetcode

Appearance

0131. 分割回文串【中等】

0131. 分割回文串【中等】 ​

1. 📝 题目描述 ​

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文串。返回 s 所有可能的分割方案。

  • 子字符串：是字符串中连续的非空字符序列。
  • 回文串：是向前和向后读都相同的字符串。

示例 1：

txt
输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]

示例 2：

txt
输入：s = "a"
输出：[["a"]]

提示：

  • 1 <= s.length <= 16
  • s 仅由小写英文字母组成

2. 🎯 s.1 - 回溯 + DP 预处理 ​

c
/**
 * Return an array of arrays of strings.
 * The sizes of these arrays are returned as *returnSize and **returnColumnSizes respectively.
 */
bool dp[16][16];
int pathStarts[16];
int pathLens[16];
int totalRows;
int totalCells;
int totalChars;
int rowIndex;
int cellIndex;
int charIndex;
char* source;
int sourceLen;
char*** answers;
int* columnSizes;
char** cellPool;
char* charPool;

void countPartitions(int start, int depth, int charsUsed) {
    if (start == sourceLen) {
        totalRows++;
        totalCells += depth;
        totalChars += charsUsed;
        return;
    }

    for (int end = start; end < sourceLen; end++) {
        if (!dp[start][end]) continue;
        countPartitions(end + 1, depth + 1, charsUsed + (end - start + 2));
    }
}

void buildPartitions(int start, int depth) {
    if (start == sourceLen) {
        answers[rowIndex] = cellPool + cellIndex;
        columnSizes[rowIndex] = depth;

        for (int i = 0; i < depth; i++) {
            int len = pathLens[i];
            answers[rowIndex][i] = charPool + charIndex;
            memcpy(charPool + charIndex, source + pathStarts[i], len);
            charIndex += len;
            charPool[charIndex++] = '\0';
        }

        cellIndex += depth;
        rowIndex++;
        return;
    }

    for (int end = start; end < sourceLen; end++) {
        if (!dp[start][end]) continue;
        pathStarts[depth] = start;
        pathLens[depth] = end - start + 1;
        buildPartitions(end + 1, depth + 1);
    }
}

char*** partition(char* s, int* returnSize, int** returnColumnSizes) {
    source = s;
    sourceLen = strlen(s);

    for (int i = sourceLen - 1; i >= 0; i--) {
        for (int j = i; j < sourceLen; j++) {
            dp[i][j] = s[i] == s[j] && (j - i < 2 || dp[i + 1][j - 1]);
        }
    }

    totalRows = 0;
    totalCells = 0;
    totalChars = 0;
    countPartitions(0, 0, 0);

    answers = (char***)malloc(sizeof(char**) * totalRows);
    columnSizes = (int*)malloc(sizeof(int) * totalRows);
    cellPool = (char**)malloc(sizeof(char*) * totalCells);
    charPool = (char*)malloc(sizeof(char) * totalChars);

    rowIndex = 0;
    cellIndex = 0;
    charIndex = 0;
    buildPartitions(0, 0);

    *returnSize = totalRows;
    *returnColumnSizes = columnSizes;
    return answers;
}
js
/**
 * @param {string} s
 * @return {string[][]}
 */
var partition = function (s) {
  const n = s.length
  const res = []
  // dp[i][j] 表示 s[i..j] 是否为回文串
  const dp = Array.from({ length: n }, () => Array(n).fill(true))
  for (let i = n - 1; i >= 0; i--) {
    for (let j = i + 1; j < n; j++) {
      dp[i][j] = s[i] === s[j] && dp[i + 1][j - 1]
    }
  }
  function backtrack(start, path) {
    if (start === n) {
      res.push([...path])
      return
    }
    for (let end = start; end < n; end++) {
      if (dp[start][end]) {
        path.push(s.slice(start, end + 1))
        backtrack(end + 1, path)
        path.pop()
      }
    }
  }
  backtrack(0, [])
  return res
}
py
class Solution:
    def partition(self, s: str) -> List[List[str]]:
        n = len(s)
        dp = [[True] * n for _ in range(n)]
        for i in range(n - 1, -1, -1):
            for j in range(i + 1, n):
                dp[i][j] = s[i] == s[j] and dp[i + 1][j - 1]
        res = []
        def backtrack(start, path):
            if start == n:
                res.append(path[:])
                return
            for end in range(start, n):
                if dp[start][end]:
                    path.append(s[start:end + 1])
                    backtrack(end + 1, path)
                    path.pop()
        backtrack(0, [])
        return res
  • 时间复杂度：O(n⋅2n)，其中 n 是字符串长度，最坏情况下有 2n−1 种分割方式
  • 空间复杂度：O(n2)，DP 表的大小

算法思路：

  • 先用 DP 预处理出 dp[i][j] 表示 s[i..j] 是否为回文串，避免回溯过程中重复判断
  • 回溯遍历所有可能的分割点，当前子串是回文串时加入路径并继续递归

Discussions